package linked_list;

import java.util.ArrayList;
import java.util.List;

public class ListOperation {
    //根据数组创建链表
    public static Node arayCreatList(){
        return null;
    }
    //手动创建结点构建链表
    public static Node manualCreatList() {
        Node n1 = new Node(100);
        Node n2 = new Node(200);
        Node n3 = new Node(300);
        Node n4 = new Node(400);
        Node n5 = new Node(500);
        Node n6 = new Node(600);
        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;
        n5.next = n6;
        n6.next = null;
        return n1;
    }
    //遍历链表并打印元素
    //只能从前往后遍历，每个结点只会经过一次
    public static void traversalList(Node head){
        Node cur = head;
        while(cur != null){
            int element = cur.val;
            System.out.println(element);
            cur = cur.next;
        }
    }
    //链表中的元素个数
    public static int elementNumberInList(Node head){
        int count = 0;
        for(Node cur = head;cur != null;cur = cur.next){
            count++;//每个结点都会经过一次，所以每个元素都会经过一次
        }
        return count;
    }
    //查找链表中某个元素所在的结点
    public static Node findElement(Node head,int target){
        //从前往后找，就是遍历整个链表中的元素和target做比较
        Node cur = head;
        while (cur != null){
            if(target == cur.val){
                //找到了相应的元素，该元素就是目前cur指向的结点中包含的元素
                return cur;
            }
            //元素不相等，则让cur指向下一个结点
            cur = cur.next;
        }
        //没有找到时返回空
        return null;
    }
    //查找链表中所有和某元素相等的结点
    private static List<Node> findEqualNode(Node head,int target){
        //创建一个对象，用来存放所有与val相等的结点
        List<Node> ans = new ArrayList<>();
        for(Node cur = head;cur != null;cur = cur.next){
            if(cur.val == target){
                //尾插
                ans.add(cur);
                //不返回，继续遍历寻找
            }
        }
        return ans;
    }
    //找到链表中的第三个结点,至少有三个结点
    private static Node findNode3(Node head){
        Node cur = head;
        //向后跳两步即可
        cur = cur.next;
        cur = cur.next;
        return cur;
    }
    //找到链表中的第n个结点，但是不保证链表的长度
    private static  Node findNthNode(Node head,int n){
        //两种可能：链表长度不足n和链表长度比n长
        Node cur = head;
        for (int i = 0; i < n - 1  && cur != null ; i++) {
            cur = cur.next;
        }
        //两种可能：
        //cur == null:说明链表长度 < n
        //cur != null:说明循环了n - 1次，向后跳了n步，，找到了第n个结点
        return cur;
    }
    //找链表的倒数第1个结点，至少有1个结点
    private static Node findLastNode1(Node head){
        Node cur = head;
        while (cur.next != null){
            cur = cur.next;
        }
        return cur;
    }
    //找链表的倒数第2个结点,至少有2个结点
    private static Node findLastNode2(Node head){
        Node cur = head;
        while (cur.next.next != null){
            cur = cur.next;
        }
        return cur;
    }
    //找链表的倒数第3个结点,至少有3个结点
    private static Node findLastNode3(Node head) {
        Node cur = head;
        while (cur.next.next.next != null) {
            cur = cur.next;
        }
        return cur;
    }
    //头插元素
    //返回值用Node，因为进行操作后需要返回新的头结点，这样才能使以后使用链表的人能够遍历整个链表
    private static Node headInsertionElement(Node head,int e){
        //先把元素装入到对应的结点中
        Node node = new Node(e);
        //两种情况：
        //链表为空：
        if(head == null){
            node.next = null;
            return node;
        }else{
            node.next = head;
            return node;
        }
        //这两种情况可以合并为一种情况，即不管链表是否为空，node.next总是要指向原来head指向的结点，这时node成为头结点，然后返回node
        //node.next = head;
        //return node;
    }
    //头插结点：不需要将元素装到一个对象里
    private static Node headInsertionNode(Node head,Node node){
        node.next = head;
        return node;
    }
    //头删
    private static Node headDeletion(Node head){
        if(head == null){
            throw new RuntimeException();
        }
        //直接返回头结点的下一个结点，就是把头结点删除了
        return head.next;
        //也可以写为：
//        if(head.next == null){
//            return head.next;
//        }else{
//            return head.next;
    }

    //尾插元素
    private static Node tailInsertionElement(Node head,int e){
        //把元素放到节点中
        Node node = new Node(e);
        //分情况处理
        if(head == null){
            node.next = null;
            return node;
        }
        Node last = head;
        while(last.next != null){
            last = last.next;
        }
        node.next = null;
        last.next = node;
        return head;
    }
    //尾插结点
    private  static  Node tailInsertionNode(Node head,Node node){
        if(head == null){
            node.next = null;
            return node;
        }
        Node last = head;
        while(last.next != null){
            last = last.next;
        }
        node.next = null;
        last.next = node;
        return head;
    }
    //尾删
    private  static Node tailDeletion(Node head){
        //空链表
        if(head == null){
            throw new RuntimeException();
        }
        //只有一个结点
        if(head.next == null){
            return null;
        }
        //找到倒数第二个结点
        Node lastOfLast = head;
        while(lastOfLast.next.next != null){
            lastOfLast = lastOfLast.next;
        }
        lastOfLast.next = null;
        return head;
    }
    //插入元素到给定结点的后边
    //不需要传入头结点，因为整个过程与头结点无关
    //指定的结点既不是头结点也不是尾结点
    private static void insertionElementToDesignatedNode(Node node,int e){
        Node newNode = new Node(e);
        newNode.next = node.next;
        node.next = newNode;
    }

    //删除给定结点后边的结点
    //指定的结点既不是头结点也不是尾结点
    private static void deleteNode(Node node){
        //找到node的下一个结点
        Node nextOfNode = node.next;
        //找到node的下一个下一个结点
        Node nextOfNext = nextOfNode.next;
        node.next = nextOfNext;
        //node.next = node.next.next;//这一句话就可以完成
    }
    public static void main(String[] args) {
        Node head = null;
        head = headInsertionElement(head,100);
        head = headInsertionElement(head,200);
        head = headInsertionElement(head,300);
        head = headInsertionElement(head,400);
        head = headInsertionElement(head,500);
        head = headInsertionElement(head,600);
        //操作后的链表：[600,500,400,300，200，100]
        traversalList(head);
        head = headDeletion(head);
        //删除后链表为：[500,400,300,200，100]
        traversalList(head);

        Node ans = findNode3(head);
        Node ans1 = findLastNode2(head);

        System.out.println(elementNumberInList(head));
        System.out.println(head);
        System.out.println(head.val);


        head = tailInsertionElement(head,10);
        //尾插结束后是：[500,400,300,200,100,10]
        traversalList(head);
        head = tailDeletion(head);
        //尾删后变为[500，400，300，200,100]
        head = tailDeletion(head);
        head = tailDeletion(head);
        head = tailDeletion(head);
        head = tailDeletion(head);
        //删到最后只剩 500 一个元素
        traversalList(head);
    }
}
